// Copyright (C) 2001-2003 Octavian Procopiuc
//
// File:    build_kdbtree.C
// Author:  Octavian Procopiuc <tavi@cs.duke.edu>
//
// Not just a test file for K-D-B-trees, but a full suite for
// constructing, querying, printing and benchmarking them. 
// It uses the run-time parameters from app_params.C
//
// $Id: build_kdbtree.C,v 1.1 2003/09/25 17:45:15 tavi Exp $

#include <sys/time.h>
#include <iomanip>
#include <iostream>

#include <portability.H>

// STL stuff.
#include <functional>
// TPIE configuration: choose BTE, block size, etc.
#include "app_config.H"
// TPIE streams and collections.
#include <ami_stream.H>
#include <ami_coll.H>
// TPIE timer.
#include <cpu_timer.H>
// The K-D-B-tree implementation.
#include <ami_kdbtree.H>
// Run-time parameters.
#include "app_params.H"

// TPIE config: choose BTE, block size, etc.
#include "app_config.H"

// TPIE streams.
#include <ami_stream.H>
#include <ami_scan.H>
#include <ami_scan_utils.H>
#include <cpu_timer.H>

#include <ami_point.H>

#if defined(COORDT_INT)
#  define COORDT int
#elif defined(COORDT_LONG)
#  define COORDT long
#elif defined(COORDT_FLOAT)
#  define COORDT float
#elif defined(COORDT_DOUBLE)
#  define COORDT double
#elif defined(COORDT_LONGLONG)
#  define COORDT long long
#else // Nothing defined.
#  define COORDT_INT
#  define COORDT int
#endif

#ifndef DIM
#  define DIM 10
#endif

#if defined(IDT_OFFT)
#  define IDT off_t
#elif defined(IDT_SIZET)
#  define IDT size_t
#elif defined(IDT_VOID)
#  define IDT void
#  define NOID
#elif defined(NOID)
#  define IDT void
#else
#  define IDT_SIZET
#  define IDT size_t
#endif

using std::ios;
using std::setiosflags;
using std::setw;


#ifdef NOID
typedef AMI_point<COORDT, DIM> point_t;
#else
typedef AMI_record<COORDT, IDT, DIM> point_t;
#endif
// Template instantiations.
#define KDBTREEint10 AMI_kdbtree<int, 10, AMI_kdtree_bin_node_small<int, 10> >
template class KDBTREEint10;

istream& operator>>(istream& s, point_t& p) {
  for (int i = 0; i < DIM; i++)
    s >> p[i];
#ifndef NOID
  return s >> p.id();
#else
  return s;
#endif
}

ostream& print_out(ostream& s, point_t& p) {
  struct timeval now;
  struct timezone tz;
  struct tm *tm;
  char buf[128];
  gettimeofday(&now, &tz);
  tm = localtime(&now.tv_sec);
  sprintf(buf, "%.2d:%.2d:%.2d.%.2d", tm->tm_hour, tm->tm_min, tm->tm_sec, now.tv_usec);    
  s.setf(ios::left, ios::adjustfield);
  s << setw (16) << buf << setw(5) << p.id() << ": ";
  for (int i = 0; i < DIM; i++)
    s << setw(10) << p[i];
   s << endl;
  return s;
}

point_t* find_point(AMI_STREAM<KDBTREEint10::point_t> *tempstr, point_t& p) {
  point_t *temp_p=NULL;

  assert(tempstr->stream_len() > 0);     

  tempstr->seek(0);  
  while (tempstr->read_item(&temp_p) == AMI_ERROR_NO_ERROR)
    if (p.id() == temp_p->id())
      return temp_p;

  return NULL;
} 

bool same(point_t& p1, point_t& p2) {
 bool ans = true;
  for (int i = 0; i < DIM; i++)
    if (p1[i] != p2[i])      
      ans = false;    
  return ans;
}

int main(int argc, char** argv) {

  KDBTREEint10* kdbtree;
  KDBTREEint10::point_t *pp;
  AMI_kdbtree_params kdb_params;
  cpu_timer atimer;
  double t_wall, t_io;

  cout << "sizeof(region_t)=" << sizeof(region_t<int,10>) 
       << "  sizeof(kdb_item_t)=" << sizeof(kdb_item_t<int,10>) << "\n";

  // <><><><><><><><><><><><><><><><><><><><>
  //    Initialize.
  // <><><><><><><><><><><><><><><><><><><><>

  // Log debugging info from the application, but not from the library. 
  tpie_log_init(TPIE_LOG_APP_DEBUG); 
 
   // Parse command-line arguments (see app_params.C)
  parse_args(argc, argv);

  params.structure_name = "KDB-TREE";

  // Set the kdbtree run-time parameters.
  kdb_params.leaf_size_max = params.leaf_size_max;
  kdb_params.node_size_max = params.node_size_max;
  kdb_params.leaf_block_factor = params.leaf_block_factor;
  kdb_params.node_block_factor = params.node_block_factor;
  kdb_params.node_cache_size = params.node_cache_size;
  kdb_params.leaf_cache_size = params.leaf_cache_size;
  kdb_params.split_heuristic = params.split_heuristic;

  // Open a kdb-tree.
  kdbtree = new KDBTREEint10(params.base_file_name_t, 
			    AMI_WRITE_COLLECTION, kdb_params);
  // Check its status.
  if (kdbtree->status() == AMI_KDBTREE_STATUS_INVALID) {
    cerr << "Error opening the kdbtree (see log for details). Aborting.\n";
    return 1;
  }
  // Set the persistency flag.
  
  kdbtree->persist(PERSIST_PERSISTENT);
  //kdbtree->persist(params.keep_tree ? PERSIST_PERSISTENT : PERSIST_DELETE);
  // Adjust some parameters to reflect the actual kdb-tree parameters,
  // in the case of an existing tree.
  params.leaf_block_factor = kdbtree->params().leaf_block_factor;
  params.node_block_factor = kdbtree->params().node_block_factor;
  // Statistics.
  add_to_stats(0, "Node capac. (keys):  ", kdbtree->params().node_size_max);
  add_to_stats(0, "Leaf capac. (items): ", kdbtree->params().leaf_size_max);
  params.stats << "Split heuristic:      "
	       << (params.split_heuristic == CYCLICAL ? "CYCLICAL": 
		   params.split_heuristic == LONGEST_SPAN ? 
		   "LONGEST_SPAN": "RANDOM") << "\n";

  cout << "Node size: " 
       << TPIE_OS_BLOCKSIZE()*params.node_block_factor 
       << " bytes. Node capacity: " 
       << KDBTREEint10::node_t::el_capacity(TPIE_OS_BLOCKSIZE()*params.node_block_factor) 
       << " elements." << "\n";

  // <><><><><><><><><><><><><><><><><><><><>
  //    Insert from input ASCII.
  // <><><><><><><><><><><><><><><><><><><><>
 
   if (params.do_insert) {
     ifstream ifs(params.file_name_in_ascii);
     ifstream ifs_temp("input_points.txt");
     ofstream ofs_temp("input_points.txt", ios::app);
     if (!ifs) {
      cerr << argv[0] << ": Error opening input points file " << params.file_name_in_ascii << "\n";
     } 
     else {
       assert(ifs != NULL);
       //assert(ifs_temp != NULL);
       //assert(ofs_temp != NULL);
       
       size_t i = 0;
       cxx_istream_scan <KDBTREEint10::point_t> in_scan(&ifs);
       cxx_istream_scan <KDBTREEint10::point_t> in_scan_temp(&ifs_temp);
       cxx_ostream_scan <KDBTREEint10::point_t> out_scan(&ofs_temp);
       AMI_STREAM<KDBTREEint10::point_t> *tempstr = 
            (params.do_query_count_only ? NULL: new AMI_STREAM<KDBTREEint10::point_t>);
       AMI_STREAM<KDBTREEint10::point_t> *tempstr2 = 
            (params.do_query_count_only ? NULL: new AMI_STREAM<KDBTREEint10::point_t>);	    
       AMI_STREAM<KDBTREEint10::point_t> *tempstr3 = 
            (params.do_query_count_only ? NULL: new AMI_STREAM<KDBTREEint10::point_t>);	    

       KDBTREEint10::point_t *pp_temp;
       cerr << "Input points from file " << params.file_name_pquery << " ...\n";
       
       
       AMI_scan(&in_scan, tempstr);       
       cout << "Reading (" << tempstr->stream_len() << " points).\n";
       bool ans;
       size_t u=0;
              
       if (AMI_scan(&in_scan_temp, tempstr3) == AMI_ERROR_NO_ERROR)
       { 
         tempstr3->seek(0);
	 
	 cerr << "Inserting1... " << flush;
         atimer.start();
         tempstr->seek(0);     

         while (tempstr->read_item(&pp) == AMI_ERROR_NO_ERROR) {
         //if (kdbtree->find(*pp))
	 pp_temp = find_point(tempstr3,*pp);
	 if (pp_temp == NULL)
         {
	   if (kdbtree->insert(*pp))
	   {
	     cerr << "i";
	     i++;
	     tempstr2->write_item(*pp);
           }            
	 }
	 else
	 {
	   if (!same(*pp_temp,*pp))	
	   {
	   //update point
	     if (kdbtree->update(*pp_temp,*pp))
             {
	       cerr << "u";
	       u++;
	       //cerr << "Point updated!" << endl;	  
	     }
	   }
	   else
	     cerr << "x";
	 }
	 }
       }
       else
       {
         cerr << "Inserting2... " << flush;
         atimer.start();
         tempstr->seek(0);     

         while (tempstr->read_item(&pp) == AMI_ERROR_NO_ERROR) {
         if (kdbtree->insert(*pp))
	 {
	   cerr << "i";
	   i++;
	   tempstr2->write_item(*pp);
         }
	 }            	 
       }	 
       AMI_scan(tempstr2,&out_scan);
       if (i > 0)
         cout << "\nDone! (" << i << ") points insert." << endl;
       if (u > 0)
         cout << "\nDone! (" << u << ") points update." << endl;
       
       atimer.stop();
       t_wall = atimer.wall_time();
       t_io = t_wall - atimer.user_time() - atimer.system_time();
       cerr << "\tInsert timings: " << atimer << "\n";
       params.stats << "INSERT (Wall IO %IO): " 
  	  << double(int(t_wall*100)) / 100 << "\t "
  	  << double(int(t_io*100)) / 100 << "\t "
  	  << (t_wall > 0 ? int(t_io*100/t_wall) : 0) << "\n";
  
       atimer.reset();
       delete tempstr;          
    }
  }

  // <><><><><><><><><><><><><><><><><><><><>
  //    Insert from input stream. (working!)
  // <><><><><><><><><><><><><><><><><><><><>  

//   if ((params.do_insert) && (params.in_stream != NULL)) {
//         
//     assert(params.in_stream != NULL);  
//     size_t i = 0;
//     params.in_stream->seek(0);
//     cerr << "Inserting..." << flush;
//     atimer.start();
//     while (params.in_stream->read_item(&pp) == AMI_ERROR_NO_ERROR) {      
//       if (kdbtree->find(*pp))
//       {
//         cerr << "x";
//       }
//       else
//       {      
//         if (kdbtree->insert(*pp)) {
// 	  cerr << ".";
// 	  i++;
//         }            
//       }
//     }
//     cout << "\nDone! (" << i << ") points insert." << endl;
//     
//     atimer.stop();
//     t_wall = atimer.wall_time();
//     t_io = t_wall - atimer.user_time() - atimer.system_time();
//     cerr << "\tInsert timings: " << atimer << "\n";
//     params.stats << "INSERT (Wall IO %IO): " 
// 	  << double(int(t_wall*100)) / 100 << "\t "
// 	  << double(int(t_io*100)) / 100 << "\t "
// 	  << (t_wall > 0 ? int(t_io*100/t_wall) : 0) << "\n";
// 
//     atimer.reset();
//     delete params.in_stream;
//     
//   }

  // <><><><><><><><><><><><><><><><><><><><>
  //    Window query from ASCII file.
  // <><><><><><><><><><><><><><><><><><><><>

  if (params.do_wquery_from_file) {
    ifstream ifs(params.file_name_wquery);
           
    if (!ifs) {
      cerr << argv[0] << ": Error opening window query file " << params.file_name_wquery << "\n";
    } else {
      size_t count = 0, result = 0;
      KDBTREEint10::point_t lop, hip;
      
      AMI_STREAM<KDBTREEint10::point_t> *tempstr = 
	(params.do_query_count_only ? NULL: new AMI_STREAM<KDBTREEint10::point_t>);
      cerr << "Window queries from file " << params.file_name_wquery << " ...\n";
      
      ofstream ofs("wquery_log.txt");
      cxx_ostream_scan<KDBTREEint10::point_t> out_scan(&ofs);
      
      atimer.start();        
      
      ifs >> lop[0] >> lop[1] >> lop[2] >> lop[3] >> lop[4] >> lop[5] >> lop[6] >> lop[7] >> lop[8] >> lop[9] >> hip[0] >> hip[1] >> hip[2] >> hip[3] >> hip[4] >> hip[5] >> hip[6] >> hip[7] >> hip[8] >> hip[9];

      while (!ifs.eof()) {
	count++;
	result += kdbtree->window_query(lop, hip, tempstr);	
	ifs >> lop[0] >> lop[1] >> lop[2] >> lop[3] >> lop[4] >> lop[5] >> lop[6] >> lop[7] >> lop[8] >> lop[9] >> hip[0] >> hip[1] >> hip[2] >> hip[3] >> hip[4] >> hip[5] >> hip[6] >> hip[7] >> hip[8] >> hip[9];
      }      
      atimer.stop();
      t_wall = atimer.wall_time();
      t_io = t_wall - atimer.user_time() - atimer.system_time();
      cerr << "\tPerformed " << count << " queries.\n";
      cerr << "\tQuery timings: " << atimer << "\n";
      cerr << "\tFound " << result << " points." << endl;
      cerr << "\tSee file wquery_log.txt for details.\n";
      //if (tempstr != NULL)
	//cerr << "\t  (real: " << tempstr->stream_len() << " points)" << endl;
      add_to_stats(0, "FQUERY:FILE          ", params.file_name_wquery);
      add_to_stats(0, "FQUERY:COUNT         ", count);
      add_to_stats(0, "FQUERY:RESULT        ", result);
      params.stats << "FQUERY:WALL_IO_%IO   "
	    << double(int(t_wall*1000))/1000 << " "
	    << double(int(t_io*100))/100 << " "
	    << int(t_io*100/t_wall) << "\n";      
      atimer.reset();
      
      //AMI_scan(tempstr,&out_scan);
      tempstr->seek(0);
      while (tempstr->read_item(&pp) == AMI_ERROR_NO_ERROR) 
	    print_out(ofs,*pp);

      delete tempstr;
    }
  }

  // <><><><><><><><><><><><><><><><><><><><>
  //    Point query from ASCII file.
  // <><><><><><><><><><><><><><><><><><><><>
  if (params.do_pquery_from_file) 
  {
    cout << params.file_name_pquery << endl;
    ifstream ifs(params.file_name_pquery);
    if (!ifs) 
    {
      cerr << argv[0] << ": Error opening point query file " << params.file_name_pquery << "\n";
    } 
    else 
    {
      ofstream ofs("pquery_log.txt");
      cxx_istream_scan<KDBTREEint10::point_t> in_scan(&ifs);
      size_t count =0, result = 0;
      AMI_STREAM<KDBTREEint10::point_t> *tempstr = 
            (params.do_query_count_only ? NULL: new AMI_STREAM<KDBTREEint10::point_t>);
       cerr << "Point queries from file " << params.file_name_pquery << " ...\n";
       atimer.start();  
       
       AMI_scan(&in_scan,tempstr);
       tempstr->seek(0);
       while (tempstr->read_item(&pp) == AMI_ERROR_NO_ERROR) 
       {
          count++;
          if (kdbtree->find(*pp)) 
	  {
	    result++;
	    print_out(ofs,*pp);
          }
       }
       atimer.stop();
       t_wall = atimer.wall_time();
       t_io = t_wall - atimer.user_time() - atimer.system_time();
       cerr << "\tPerformed " << count << " queries.\n";
       cerr << "\tQuery timings: " << atimer << "\n";
       cerr << "\tFound " << result << " points." << endl;
       cerr << "\tSee file pquery_log.txt for details.\n";
       //cerr << "\t  (real: " << tempstr->stream_len() << " points)" << endl;
       add_to_stats(0, "FQUERY:FILE	     ", params.file_name_pquery);
       add_to_stats(0, "FQUERY:COUNT	     ", count);
       add_to_stats(0, "FQUERY:RESULT	     ", result);
       params.stats << "FQUERY:WALL_IO_%IO   "
	  << double(int(t_wall*1000))/1000 << " "
	  << double(int(t_io*100))/100 << " "
	  << int(t_io*100/t_wall) << "\n";	
       atimer.reset();
       delete tempstr;
     }
  }  

  // <><><><><><><><><><><><><><><><><><><><>
  //    Print tree (DFS in-order).
  // <><><><><><><><><><><><><><><><><><><><>

  if (params.do_display) {
    int level = -1;
    kdb_item_t<int, 10> ki;
    cout << "DFS: ";
    do {
      ki = kdbtree->dfs_preorder(level);
      cout << "(" << ki.bid << (ki.type == BLOCK_NODE? 'B':'L') << level << ") ";
    } while (level > -1);
    cout << endl;
  }


  // <><><><><><><><><><><><><><><><><><><><>
  //    Clean up and print statistics.
  // <><><><><><><><><><><><><><><><><><><><>
  
  tpie_stats_tree bts;
  params.point_count = kdbtree->size();
  bts = kdbtree->stats();
  params.stats << "Space utilization:    " 
       << (kdbtree->size() * sizeof(KDBTREEint10::point_t) * 100.00 / 
	   (kdbtree->stats().get(LEAF_COUNT) * kdbtree->leaf_block_size() + 
	    kdbtree->stats().get(NODE_COUNT) * kdbtree->node_block_size()))
	       << "%\n";
  delete kdbtree;

  params.write_block_stats(bts);

  print_configuration();
  print_statistics();

  // Write statistics to a file (append).
  ofstream ofs(params.file_name_stats, ios::app);
  print_configuration(ofs);
  print_statistics(ofs);

  return 0;
}
